package LeetCode;

import java.util.Stack;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}15:58
 */
public class LeetCode557 {
    // 暴力解法
    public String reverseWords(String s) {
        if (s.length() == 0){
            return s;
        }
        // 先进行一个分割
        String[] arr = s.split(" ");
        StringBuilder builder = new StringBuilder();
        for (String s1 : arr) {
            Stack<Character> stack = new Stack<>();
            for (char c : s1.toCharArray()) {
                stack.push(c);
            }
            while (!stack.isEmpty()){
                builder.append(stack.pop());
            }
            builder.append(" ");
        }
        builder.deleteCharAt(builder.length() - 1);
        return builder.toString();
    }

    // 原地解法 空间最优
    // 此题也可以直接在原字符串上进行操作，避免额外的空间开销。当找到一个单词的时候，我们交换字符串第一个字符与倒数第一个字符，随后交换第二个字符与倒数第二个字符…… 如此反复，就可以在原空间上翻转单词。
    public String reverseWords2(String s) {
        char[] value = new char[s.length()];
        int ws = 0, i = 0,count = 0;
        while (i <= s.length()) {
            if (i < s.length() && s.charAt(i) != ' ') {
                i++;
                continue;
            }
            for (int j = i - 1; j >= ws; j--) {
                value[count++] = s.charAt(j);
            }
            if (i < s.length()) value[count++] = ' ';
            ws = ++i;
        }
        return new String(value);
    }


    //需要注意的是，原地算法在某些语言（比如 Java，JavaScript）中不适用，因为在这些语言中 String 类型是一个不可变的类型。
    public static void main(String[] args) {
        String s = "Let's take LeetCode contest";
        System.out.println(new LeetCode557().reverseWords(s));
    }
}
